package words;

import java.util.ArrayList;
import java.util.List;

/**
 * 数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
 * <p>
 *  
 * <p>
 * 示例：
 * <p>
 * 输入：n = 3
 * 输出：[
 * "((()))",
 * "(()())",
 * "(())()",
 * "()(())",
 * "()()()"
 * ]
 * 1. 嵌套包含
 * 2. 一个包着其它
 * 3.
 */
public class Barckets {
    public static void main(String[] args) {
        List<String> result = new ArrayList<>();
        generate(0, new char[2 * 1], result);
        for (String s : result) {
            System.out.println(s);
        }
    }

    public static void generate(int pos, char[] current, List<String> result) {
        if (pos == current.length) {
            if (valid(current)) {
                result.add(new String(current));
            }
        } else {
            // 列出所有组合
            current[pos] = '(';
            System.out.println("左括号" + pos);
            generate(pos + 1, current, result);
            current[pos] = ')';
            System.out.println("右括号" + pos);
            generate(pos + 1, current, result);
        }
    }

    public static boolean valid(char[] current) {
        int balance = 0;
        for (char ch : current) {
            if (ch == '(') {
                balance++;
            } else {
                balance--;
                if (balance < 0) {
                    return false;
                }
            }
        }
        return balance == 0;
    }

}
